package tree.impl;

import tree.Tree;

import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;

/** User: Vitalii Serdiuk
  * Date: 27.11.13 14:42
  */
public class BinaryTree<T extends Comparable> implements Tree<T> {
    private Node<T> root;
    private int size;

    public BinaryTree() {
        size = 0;
    }

    public BinaryTree(Node<T> root, int size) {
        this.root = root;
        this.size = size;
    }

    private Node<T> find0(T data) {
        Node<T> treeNode = root;
        while (treeNode != null) {
            int resultCompare = data.compareTo(treeNode.data);
            if (resultCompare < 0)
                treeNode = treeNode.left;
            if (resultCompare > 0)
                treeNode = treeNode.right;
            if (resultCompare == 0)
                return treeNode;
        }
        return null;
    }

    public boolean exist(Node<T> findNode) {
        return find0(findNode.data) != null;
    }

    public Node<T> find(Node<T> findNode) {
        Node<T> node = find0(findNode.data);
        if (node == null) {
            throw new NoSuchElementException(findNode.toString());
        }
        return node;
    }

    public void add(T data) {
        if (root == null) {
            root = new Node<T>(data, null);
        } else {
            Node<T> node = root;
            Node<T> tempNode;
            do {
                int resultCompare = data.compareTo(node.data);

                if (resultCompare < 0) {
                    tempNode = node.left;
                    if (tempNode == null) {
                        node.left = new Node<T>(data, node);
                        break;
                    } else {
                        node = tempNode;
                    }
                } else if (resultCompare >= 0) {
                    tempNode = node.right;
                    if (tempNode == null) {
                        node.right = new Node<T>(data, node);
                        break;
                    } else {
                        node = tempNode;
                    }
                }
            } while (node != null);
        }
        size++;
    }


    public void remove(T data) {
        Node<T> remNode = find0(data);
        Node<T> parentNode;

        if (!remNode.equals(root)) {
            parentNode = remNode.parent;


            if (remNode.left == null) {
                if (remNode.right == null) {
                    if (parentNode.left == remNode) {
                        parentNode.left = null;
                    }
                    if (parentNode.right == remNode) {
                        parentNode.right = null;
                    }
                } else if (remNode.right != null) {
                    if (parentNode.left == remNode) {
                        parentNode.left = remNode.right;
                    } else if (parentNode.right == remNode) {
                        parentNode.right = remNode.right;
                    }
                }
            }

            if (remNode.right == null) {

                if (remNode.left == null) {
                } else {
                    if (parentNode.right == remNode) {
                        parentNode.right = remNode.left;
                    } else if (parentNode.left == remNode) {
                        parentNode.left = remNode.left;
                    }
                }
            }


            if (remNode.left != null && remNode.right != null) {
                Node<T> tempNode = findLeftNodeInRightSubtree(remNode);
                if (parentNode.left == remNode) {
                    tempNode.parent.left = null;
                    tempNode.parent = parentNode;
                    tempNode.left = remNode.left;
                    tempNode.right = remNode.right;
                    parentNode.left = tempNode;

                } else {
                    tempNode.parent.right = null;
                    tempNode.parent = parentNode;
                    parentNode.right = tempNode;

                }
            }
        }else{
            Node<T> tempNode = findLeftNodeInRightSubtree(remNode);

            tempNode.parent=null;
            if(root.left!= tempNode)
                tempNode.left=root.left;
            if(root.right!= tempNode)
                tempNode.right = root.right;
            root = tempNode;

        }
        size--;
    }

    public int getSize() {
        return size;
    }

    private Node<T> findLeftNodeInRightSubtree(Node<T> remNode) {
        Node<T> tempNode = remNode.right;
        Node<T> leftNodeInRightSubtree = remNode.right;
        while (leftNodeInRightSubtree != null) {
            tempNode = leftNodeInRightSubtree;
            leftNodeInRightSubtree = leftNodeInRightSubtree.left;
        }
        return tempNode;
    }

    public void removeAll() {
        root = null;
        size = 0;
    }

    public void deepOut() {
        deepOut0(root, 0);
    }

    private void deepOut0(Node<T> node, int depth) {
        if (node == null) return;
        deepOut0(node.left, ++depth);
        deepOut0(node.right, ++depth);
        System.out.print(" " + node.data);

    }

    public void wightOut() {
        contLevelOrder(root, size);
    }

    void contLevelOrder(Node<T> top, int size) {
        Queue<Node<T>> queue = new LinkedList<Node<T>>();
        System.out.print(top.data + " ");
        do {
            if (top.left != null) queue.add(top.left);
            if (top.right != null) queue.add(top.right);

            if (!queue.isEmpty()) {
                top = queue.poll();
                size--;
            }
            System.out.print(top.data + " ");
        } while (size > 0);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof BinaryTree)) return false;

        BinaryTree binaryTree = (BinaryTree) o;

        return !(root != null ? !root.equals(binaryTree.root) : binaryTree.root != null);

    }

    @Override
    public int hashCode() {
        return root != null ? root.hashCode() : 0;
    }

    @Override
    public String toString() {
        return "BinaryTree{" +
                "root=" + root +
                '}';
    }
}

